#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NODE 10

typedef struct Node {
  int key, ltag, rtag;
  Node *lchild, *rchild;
} Node;

Node *pre_node, *inorder_root;

Node *getNewNode(int key) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->key = key;
  p->ltag = p->rtag = 0;
  p->lchild = p->rchild = NULL;
  return p;
}

void clear(Node *root) {
  if (root == NULL)
    return;
  if(root->ltag == 0) clear(root->lchild);
  if(root->rtag == 0) clear(root->rchild);
  free(root);
  return;
}

Node *insertNode(Node *root, int key) {
  if (root == NULL)
    return getNewNode(key);
  if (rand() % 2)
    root->lchild = insertNode(root->lchild, key);
  else
    root->rchild = insertNode(root->rchild, key);
  return root;
}

void pre_order(Node *root){
  if(root == NULL) return;
  printf("%d ", root->key);
  if(root->ltag == 0) pre_order(root->lchild);
  if(root->rtag == 0) pre_order(root->rchild);
  return;
}

void in_order(Node *root){
  if(root == NULL) return;
  if(root->ltag == 0) in_order(root->lchild);
  printf("%d ", root->key);
  if(root->rtag == 0) in_order(root->rchild);
  return;
}

void post_order(Node *root){
  if(root == NULL) return;
  if(root->ltag == 0) post_order(root->lchild);
  if(root->rtag == 0) post_order(root->rchild);
  printf("%d ", root->key);
  return;
}

void __build_inorder_thread(Node *root){
  if(root == NULL) return;
  if(root->ltag == 0) __build_inorder_thread(root->lchild);
  if(inorder_root == NULL) inorder_root = root;
  // update thread of previous node
  if(root->lchild == NULL){
    root->lchild = pre_node;
    root->ltag = 1;
  }
  // update thread of next node
  if(pre_node && pre_node->rchild == NULL){
    pre_node->rchild = root;
    pre_node->rtag = 1;
  }
  pre_node = root;
  if(root->rtag == 0) __build_inorder_thread(root->rchild);
  return;
}

void build_inorder_thread(Node *root){
  __build_inorder_thread(root);
  // update last node 
  pre_node->rchild = NULL;
  pre_node->rtag = 1;
  return;
}

Node *getNext(Node *root){
  if(root->rtag == 1) return root->rchild;
  root = root->rchild;
  while (root->ltag == 0) root = root->lchild;
  return root;
}

int main() {
    srand(time(0));
    Node *root = NULL;
    pre_node = NULL;
    inorder_root = NULL;
    for(int i = 0; i < MAX_NODE ; i++){
        root = insertNode(root, rand() % 100);
    }
    build_inorder_thread(root);
    printf("preorder:\t");
    pre_order(root);
    printf("\n");
    printf("inorder:\t");
    in_order(root);
    printf("\n");
    printf("postorder:\t");
    post_order(root);
    printf("\n");
    // like linklist
    printf("inorder_thread:\t");
    Node *node = inorder_root;
    while(node){
      printf("%d ",node->key);
      node = getNext(node);
    }
    printf("\n");
    clear(root);

  return 0;
}
